package com.learn.algorithm.list;

public class MergeTwoList {

    /**
     * 合并两个有序链表
     */

    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        // 边界条件 如果其中一个链表为null 直接返回另一个链表
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        // 1. 找到合并后链表的头部
        ListNode head = head1.val <= head2.val ? head1 : head2;
        // 2. 使用两个指针分别指向两个链表中待比较的第一个节点 注意: head已经指向头部了, 所以cur1指向了head.next
        ListNode cur1 = head.next;
        ListNode cur2 = head == head1 ? head2 : head1;
        // 3. 记录当前已排好序的最后一个节点的位置
        ListNode pre = head;
        while (cur1 != null && cur2 != null) {
            // 4. 比较待排序节点中的值
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        // 当一个节点到头后 将pre.next指向未处理完成的链表
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }
}
